package leetcode.dp;

public class A1143 {


    //s(i,j):以下标i,j为终点的公共子序列的最大值
    //res=(s(i,j),s(i-1,j),s(i,j-1),s(i-1,j-1))取MAX  ==》
    //如果i,j元素相等,那么res=s(i-1,j-1)+1
    //如果不相等 res=s(i-1,j),s(i,j-1) 取MAx 为什么舍弃s(i-1,j-1)，因为他包含在前面两种结果中
    public int longestCommonSubsequence1(String text1, String text2) {
        int len1= text1.length();
        int len2 = text2.length();
        int[][] dp=new int[len1+1][len2+1];
     //左上边界均为0
        //枚举长度
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else dp[i][j] =Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
    //滚动数组空间优化
    //我们当前要获取的值，从左和上和左上转换而来，所以，但是，左上的值会被左覆盖，所以我们在处理当前值后，要先记录当前值，供右值使用
    public int longestCommonSubsequence(String text1, String text2) {
        String str1;
        String str2;
        str1=text1.length()<text2.length()?text1:text2;//str1为长度短的
        str2=text1.length()<text2.length()?text2:text1;
        int len1= str1.length();//短
        int len2 = str2.length();//长
        int[] dp=new int[len1+1];
        //左上边界均为0

      for(int i=1;i<=len2;i++){//枚举次数
          int leftUp=0,temp;
          for(int j=1;j<=len1;j++)     //枚举长度
          {
              temp=dp[j];
            if(str2.charAt(i-1)==str1.charAt(j-1))dp[j]=1+leftUp;
            else dp[j]=Math.max(dp[j-1],dp[j]);
              //记录当前情况
            leftUp=temp;
          }
      }
        return dp[len1];
    }

}
